#include <bits/stdc++.h>
using namespace std;
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using ll = long long;
ll mp[20][20], d[20][20], vis[20][20];
ll h[200], lie[200], xie_z[200],xie_y[200];
ll a[200];
ll n;
ll ans;
void dfs(ll step)
{
    if(step>n)
    {
        ans++;
        if(ans<=3)
        {
            for(ll i=1;i<=n;i++)
            {
                cout << a[i] << " ";
            }
            cout << endl;
        }
        return;
    }

    for(ll i=1;i<=n;i++)
    {
        if(!lie[i]&&!xie_z[step-i+n]&&!xie_y[step+i])
        {
            a[step]=i;
            lie[i]=1;
            xie_z[step - i + n] = 1;
            xie_y[step + i] = 1;
            dfs(step + 1);
            lie[i] = 0;
            xie_z[step - i + n] = 0;
            xie_y[step + i] = 0;
        }
    }
}
void solve()
{

    cin >> n;
    dfs(1);
    cout << ans;
}
int main()
{
    int t = 1;
//    cin >> t;
    while(t--)
    {
        solve();
    }
   return 0;
}
